package com.wyw.leetcode.learning.medium;

import com.wyw.leetcode.simple.parent.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * leetcode topic 19
 * 删除链表中倒数第N个节点
 * @Author Mr Wu （yewen.wu.china@gmail.com）
 * @Date 2021/11/9 14:09
 */
public class Topic019 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
//        ListNode listNodeNew = new ListNode(2);
//        listNodeNew.next = listNode;
//        listNode = listNodeNew;
        for(int i=2; i< 7; i++) {
            ListNode listNodeNew = new ListNode(i);
            listNodeNew.next = listNode;
            listNode = listNodeNew;
        }
//        removeNthFromEnd1(listNode, 1);
        removeNthFromEnd2(listNode, 2);

    }

    //最简单的实现就是先扫描一次表，然后计算出链表长度，第二次在截取
    public static ListNode removeNthFromEnd1(ListNode head, int n) {

        ListNode newListNode = null;
        while (head.next != null) {
            ListNode listNodeNew = new ListNode(head.val);
            listNodeNew.next = newListNode;
            newListNode = listNodeNew;
            head = head.next;
        }
        ListNode listNodeNew1 = new ListNode(head.val);
        listNodeNew1.next = newListNode;
        newListNode = listNodeNew1;


        ListNode result = null;
        int i = 1;
        while( newListNode != null && newListNode.next != null) {
            if(i == n) {
                newListNode = newListNode.next;
            }
            ListNode listNodeNew = new ListNode(newListNode.val);
            listNodeNew.next = result;
            result = listNodeNew;
            newListNode = newListNode.next;
            i++;
        }
        if(i == n || newListNode == null) {
            return result;
        }
        ListNode listNodeNeww = new ListNode(newListNode.val);
        listNodeNeww.next = result;
        result = listNodeNeww;
        return result;
    }

    /**
     * 官方建议的双指针
     */
    public static ListNode removeNthFromEnd2(ListNode head, int n) {

        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    /**
     * 官方  计算链表长度
     */
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
    public static int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }

    /**
     * 栈
     */
    public static ListNode removeNthFromEnd4(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

}


